package LinkedList;

/**
 * 题目 ：
 * 给定两个 非空链表 l1和 l2来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *
 * 注意 ：可以假设除了数字 0 之外，这两个数字都不会以零开头。
 */
public class OfferP25 {
    /**
     *  核心思想 ：
     *  （1）由于链表存储时（数字：高位 - 低位），反转链表（数字 ：低位 - 高位）
     *  （2）链表相加操作（注意 ：数字之间的进位）
     *  （3）将相加的结果链表，再次反转
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1.反转链表（即，数字 ：低位 - 高位）
        ListNode head1 = reverseList(l1);
        ListNode head2 = reverseList(l2);
        // 2.链表相加（注意进位）
        ListNode newHead = listAdd(head1, head2);
        // 3.反转链表（将相加链表中的数字 ：高位 - 低位）
        return reverseList(newHead);
    }
    public ListNode listAdd(ListNode head1 , ListNode head2){
        // 1. 建立哨兵节点(哨兵节点不变)
        ListNode dummy = new ListNode(0);
        // 2. 定义一个节点，指向哨兵节点（可以对其节点进行移动和修改）
        ListNode now = dummy;
        // 3. 保持进位值
        int carry = 0;
        // 4. 遍历所有传入的链表，直至为空链表（即，此循环将构建一条两条链表相加之后的新链表）
        while(head1 != null || head2 != null){
            int sum = (head1 == null ? 0 : head1.val) + (head2 == null ? 0 : head2.val) + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum -10 : sum;
            // 5.此处是将两条链表的低位相加的结果，以链表节点的形式插入到一条新构建的链表中去
            ListNode sumNode = new ListNode(sum); // 定义一个链表节点，来保存链表中各位数字相加的值
            now.next = sumNode; // 使得链表的next指针，指向上面定义的节点
            now = sumNode; // 将now节点指向其next节点（即，逐步构建一个相加链表）
            // 6.遍历两条所传入需要进行运算的链表（head1，head2进行向next指针移动）
            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
        }
        // 7.即，上述循环只判断到最高位，
        // 特殊情况 ：若是最高位发生进位的话，需要进行额外的考虑
        if(carry > 0){
            ListNode sumNode = new ListNode(carry);
            now.next = sumNode;
        }
        return dummy.next;
    }
    // 链表反转（使用prev（指向上一个节点），now（当前节点），next指针（下一个节点），进行链表的反转）
    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode now = head;
        while (now != null){
            ListNode next = now.next;
            now.next = prev;
            prev = now;
            now = next;
        }
        return prev;
    }
}
